package tree;

import java.util.*;

/**
 * AVL：本质上 AVL 数就是一颗平衡二叉树，也是二分搜索树
 */
public class AVLTree<E extends Comparable<E>> {

    private class Node{
        public E e;
        public Node left;
        public Node right;
        public int height;  //  节点高度值为1

        public Node(E e){
            this.e = e;
            left = null;
            right = null;
            height = 1;
        }

    }


    private Node root;
    private int size;

    public int size(){
        return size;
    }

    //获取节点高度
    private int getHeight(Node node){
        if(node == null){
            return 0;
        }

        return node.height;
    }

    // 获取节点的平衡因子，平衡因子 >= 2 表示向左倾斜，平衡因子 <= -2 表示向右倾斜
    private int getBalanceFactor(Node node){
        if(node == null){
            return 0;
        }

        return getHeight(node.left) - getHeight(node.right);
    }


    public boolean isEmpty(){
        return size==0;
    }

    // 判断该二叉树是否为一颗二分搜索树
    public boolean isBST(){
        //使用中序遍历，结果如果是顺序的，那么这棵树就是二分搜索树，否则就不是
        ArrayList<E> data = new ArrayList<>();
        inOrder(root,data);
        for (int i = 1; i <= data.size(); i++) {
            if( data.get(i-1).compareTo(data.get(i)) > 0 ){
                //中序遍历结果不是升序结果，该树不为二分搜索树
                return false;
            }
        }
        return true;
    }

    // 判断这棵树是否为平衡二叉树
    public boolean isBalanced(){
        return isBalanced(root);
    }
    // 返回值为：这棵树是否为平衡二叉树
    private boolean isBalanced(Node node){
        if(node == null){
            return true;
        }

        int balanceFactor = getBalanceFactor(node);
        if(Math.abs(balanceFactor) > 1){    //平衡因子的绝对值大于1，表示不是平衡二叉树
            return false;
        }

        //左子树是否为平衡二叉树
        boolean leftIsBalanced = isBalanced(node.left);
        //右子树是否为平衡二叉树
        boolean rightIsBalanced = isBalanced(node.right);
        return  leftIsBalanced && rightIsBalanced;
    }

    /**
     * LL情况：先将 y 放到 x 的右孩子上，再将 x 之前的右孩子，放在 y 的左孩子上
     * 右旋转
     * @param y：
     * @return
     *
     *          y                                        x
     *         / \                                     /   \
     *        x   t4            右旋转                 z    y
     *       / \            - - - - - - - - ->      / \   / \
     *      z  t3                                  t1 t2 t3 t4
     *     / \
     *   t1  t2
     */
    private Node rightRotate(Node y){

        Node x = y.left;
        Node t3 = x.right;

        //向右旋转过程
        x.right = y;
        y.left = t3;

        // 更新height，先更新y的 height，再更新x的 height
        y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;
        x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;

        return x;



    }

    /**
     * RR 情况
     * 左旋转
     * @param y：
     * @return
     *
     *          y                                        x
     *         / \                                     /   \
     *       t1   x            左旋转                  y    z
     *           / \        - - - - - - - - ->      / \   / \
     *          t2  z                             t1 t3 t3  t4
     *             / \
     *            t3 t4
     */
    private Node leftRotate(Node y){
        Node x = y.right;
        Node t2 = x.left;

        //左旋转
        x.left = y;
        y.right = t2;

        // 更新height，先更新y的height，再更新x的height
        y.height = Math.max(getHeight(y.left) , getHeight(y.right)) + 1;
        x.height = Math.max( getHeight(x.left) , getHeight( x.right)) + 1;

        return x;
    }


    /**
     * LR 情况，首先对 x 进行左旋转,将其转化为 LL 的情况,再右旋转
     * 右旋转
     * @param y：
     * @return
     *
     *          y                                        x
     *         / \                                     /   \
     *        x   t4            右旋转                 z    y
     *       / \             - - - - - - - - ->      / \   / \
     *      t1  z                                   t1 t2 t3 t4
     *         / \
     *       t2  t3
     */


    //为二分搜索树添加元素：递归
    public void add(E e){
        root = add(root,e);

    }

    //返回插入新节点后二分搜索树的根节点
    private Node add(Node node, E e){

        if(node == null){
            size++;
            return new Node(e);
        }

        if(e.compareTo(node.e) < 0){
            node.left = add(node.left,e);
        }else if(e.compareTo(node.e) > 0){
            node.right = add(node.right,e);
        }

        node.height =  1 + Math.max(getHeight(node.left),getHeight(node.right));

        // 计算平衡因子
        int balanceFactor = getBalanceFactor(node);
        // 维护平衡性

        // LL 情况
        if(balanceFactor >= 2 && getBalanceFactor(node.left) >= 0){  //当前node不平衡，是因为左侧的左侧添加了一个新节点，当前树向左倾斜
            return rightRotate(node);
        }

        // RR 情况
        if(balanceFactor <= -2 && getBalanceFactor(node.right) <= 0){    //当前树向右倾斜,需要右旋转
            return leftRotate(node);
        }

        // LR 情况
        if( balanceFactor > 1 && getBalanceFactor(node.left) < 0 ){
            node.left = leftRotate(node.left);
            return rightRotate(node);
        }

        // RL 情况
        if( balanceFactor < -1 && getBalanceFactor(node.right) > 0 ){
            node.right = rightRotate(node.right);
            return leftRotate(node);

        }
        return node;
    }

    //二分搜索树——前序遍历
    public void preOrder(){
        preOrder(root);
    }

    private void preOrder(Node node){
        if(node == null){
            return ;
        }

        preOrder(node.left);
        preOrder(node.right);
    }

    public void inOrder(){
        inOrder(root);
    }

    //中序遍历以node为根的二分搜索树，递归算法
    private void inOrder(Node node){
        if(node == null){
            return ;
        }

        inOrder(node.left);
        System.out.println("中序遍历");
        inOrder(node.right);
    }

    private void inOrder(Node node, List<E> array){
        if(node == null){
            return;
        }

        inOrder(node.left, array);
        array.add(node.e);  //中序遍历
        inOrder(node.right, array);
    }

    //后续遍历
    public void postOrder(){
        postOrder(root);
    }

    private void postOrder(Node node){
        if(node == null){
            return ;
        }

        postOrder(node.left);
        postOrder(node.right);
        //后续遍历所做的事
        System.out.println(node.e);
    }

    //前序遍历-非递归算法，使用栈
    public void preOrderNR(){
        Stack<Node> stack = new Stack<Node>();
        stack.push(root);
        while (!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);

            if(cur.right != null){
                stack.push(cur.right);
            }
            if(cur != null){
                stack.push(cur.left);
            }
        }
    }

    //层序遍历/广度优先遍历
    public void levelOrder(){
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while (!q.isEmpty()){
            Node cur = q.remove();
            System.out.println(cur.e);

            if(cur.left != null){
                q.add(cur.left);
            }

            if(cur.right != null){
                q.add(cur.right);
            }
        }
    }

    //查找二分搜索树中的最小值：左子树中，没有左孩子的节点，就是最小值
    public E minimum(){
        if(size == 0){
            //二分搜索树中没有元素
            throw new IllegalArgumentException("没有元素");
        }

        return minimum(root).e;
    }

    //返回Node为根的二分搜索树节点
    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }

        return minimum(node.left);

    }

    //删除二分搜索树最小值节点，要注意该节点是叶子节点还是根节点
    public E removeMin(){
        E ret = minimum();
        removeMin();

        return ret;
    }
    //删除掉以node为根的二分搜索树中的最小节点
    //返回删除节点后的新二分搜索树的根
    private AVLTree.Node removeMin(AVLTree.Node node){
        if(node.left == null){
            AVLTree.Node rightNode = node.right;
            //删除元素
            node.right = null;
            size--;
            return rightNode;
        }

        node.left = removeMin(node.left);
        return node;
    }


    //查找二分搜搜树中，最大值节点
    public E maximum(){
        if(size == 0){
            throw new IllegalArgumentException("没有元素");
        }

        return maximum(root).e;
    }

    //返回二分搜索树中，最大值的根节点
    private Node maximum(AVLTree.Node node){
        if(node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    //删除最大值的节点，返回删除节点后的新子树的根节点
    private Node removeMax(Node node){
        if(node.right == null){
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        node.right = removeMax(node.right);
        return node;
    }

}
